The present invention relates to a Montgomery reduction apparatus and a storage medium which are suitable for repetition of arithmetic processing including multiple-length multiplication using an odd integer as a modulus, e.g., public key encryption used for encryption of data in data communication over a computer network and authentication of a communication partner.
In an information communication network or computer system, electronic data are exchanged and accumulated. When such a system increases in size and an unspecified large number of users use the system, tapping and tampering by malevolent users become problems. To solve these problems, the public key encryption technique is often used.
In many cases, public key encryption is implemented by arithmetic operation (remainder computation system) using a multiple-length odd integer as a modulus. The speed of this arithmetic operation influences the performance of this scheme. In the remainder computation system, multiplication and division, in particular, exert great influences on the processing time. For example, in RSA encryption, encryption and decryption are executed by power calculations in a remainder computation system using an odd composite number as a modulus. In elliptic curve encryption on a prime field Fp, addition of points on an elliptic curve is implemented by an appropriate combination of addition, subtraction, multiplication, and division using an odd prime number as a modulus, and encryption and decryption are executed by repetition of the point addition operation.
When a multiplication (calculation of A*B mod p) in a remainder computation system is to be implemented, a multiple-length multiplication (calculation of C=A*B) and a multiple-length remainder calculation (calculation of C mod p) with respect to the multiplication result are often configured. In this case, the performance of a multiple-length remainder calculation tends to be inferior to that of a multiple-length multiplication, and hence several studies have been made on the efficiency of remainder calculations.
As a calculation algorithm suitable for repetitive execution of multiplication in a remainder computation system, the Montgomery calculation is known.
According to a Montgomery calculation method, multiplication in a remainder computation system using an odd integer as a modulus is executed as follows. First of all, a multiple-length multiplication of a multiplier A and a multiplicand B is executed to obtain C. Assume that A and B are equal to or smaller in size than an integer p as a modulus. A computation called Montgomery reduction is then performed for C to reduce its size to that of the modulus or less. That is, C having a size about twice that of the modulus p is reduced to that of the modulus p. The Montgomery reduction corresponds to a general remainder calculation. The processing amount for this operation is almost equal to that for one multiplication of multiple-length values. That is, the remainder calculation processing is made efficient. This is because, of arithmetic operations on a computer, division is time-consuming operation as compared with addition, subtraction, and multiplication.
The Montgomery calculation method is an algorithm suitable for repetitive execution of multiplication in a remainder computation system for the reason given below. The Montgomery calculation method is a multiplication algorithm using an element in a Montgomery operation domain (this is also a remainder system with the same modulus), and the following processing is required to implement a multiplication in a general remainder system. First of all, a multiplier and a multiplicand are converted into values in the Montgomery operation domain. A Montgomery multiplication (multiplication and Montgomery reduction) is then performed. Lastly, the result must be inversely converted from the Montgomery operation domain to the original remainder system. The correspondence between the elements in the Montgomery operation domain and the original remainder system is stored before and after the Montgomery multiplication. Assume that multiplication is to be repeated in the remainder computation system as in power calculation. In this case, if the base of a power is converted into a value in the Montgomery operation domain at first, the Montgomery multiplication result need not be inversely converted into a value in the original remainder system every time the result is obtained. The result can be repeatedly used as an input for Montgomery multiplication. It therefore suffices if the value in the Montgomery operation domain is converted into a value in the original remainder system as the end of power calculation. The computation sizes for conversion and inverse conversion to and from the Montgomery computation respectively correspond to one remainder calculation and one multiplication. When such operation is performed only once at the beginning and start of the overall processing, no overhead occurs.
Elements in the Montgomery operation domain and the general remainder system have the following relationship. First of all, a power of 2 which is prime relative to the modulus p and larger than the modulus p is defined as R. In general, R is often set as a value that is a multiple of the word size of a computer and the minimum value exceeding the size of the modulus p. Consider, for example, software for a 32-bit CPU, and 1,024bits the modulus p. In this case, if R=21024 (=(232)32), and the modulus p is 160 bits, R=2160 (=(232)5).
If elements in the general remainder system are represented by a and b with R described above, elements in the Montgomery operation domain which correspond to the elements a and b are represented by A=aR(mod p) and B=bR(mod p). In Montgomery reduction, D=CRxe2x88x921(mod p)=(ab)R(mod p) is calculated with respect to C=AB. The element D in the Montgomery operation domain corresponds to the values a and b in the general remainder system. Montgomery reduction is arithmetic operation equivalent to D=CRxe2x88x921(mod p), and hence can also be used for inverse conversion of the element D in the Montgomery operation domain to an element d in the general remainder system. That is, d=DRxe2x88x921(mod p)=ab(mod p).
This Montgomery reduction is main arithmetic processing in Montgomery operation, and the processing speed of this arithmetic operation greatly influences the speed of encryption and the like. This arithmetic operation corresponds to about one multiple-length multiplication and hence is efficient as compared with computation methods other than the Montgomery computation method. Demands, however, have arisen for an increase in processing speed in consideration of the recent spread of encryption techniques and the like.
At present, there is no technique implemented, which can greatly reduce the processing amount of Montgomery reduction beyond one multiple-length multiplication. In practice, therefore, even the use of a Montgomery computation system cannot sufficiently improve the computation efficiency.
The present invention has been made in consideration of the above situation, and has as its object to provide a Montgomery reduction apparatus which can implement Montgomery reduction with a small calculation amount and greatly improve the efficiency of Montgomery reduction.
It is another object of the present invention to provide an elliptic curve encryption apparatus using the Montgomery reduction apparatus.
In order to achieve the above objects, according to the first aspect of the present invention, there is provided a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=Cxc2x7Rxe2x88x921 mod p by using R defined as R=2n using an integer a falling within a range nxe2x89xa7L with a bit length being represented by L when p is expressed in binary notation, comprising:
an (xcex1, xcex2) extraction section for calculating an integer pair (xcex1, xcex2) satisfying C=xcex1R+xcex2 on the basis of C and R;
a multiplication section for obtaining xcex5xcex2 by multiplying xcex5 satisfying Rxe2x88x921=xcex5(mod p) and xcex2 calculated by the (xcex1, xcex2) extraction section;
an addition section for obtaining xcex1+xcex5xcex2 by adding xcex1 calculated by the (xcex1, xcex2) extraction section and xcex5xcex2 calculated by the multiplication section; and
a calculation section for obtaining a remainder D=xcex1+xcex2xc2x7xcex5(mod p) which is congruent to xcex1+xcex5xcex2 obtained by the addition section with respect to p as a modulus and is not more than p.
According to the present invention, if, for example, xcex5 is a value equal to or less than one word of the computer, the calculation to be performed by the multiplication section is a multiplication of a 1-word integer and a multiple-length integer. In addition, since the execution result obtained by the addition section becomes larger by about one word, it suffices if the last calculation section performs remainder calculation processing to reduce the data by one word. Since the computation size in other portions is small, a reduction in the overall processing amount can be achieved.
According to the second aspect of the present invention, there is provided a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=Cxc2x7Rxe2x88x921 mod p by using R defined as R=2n using an integer n falling within a range nxe2x89xa7L with a bit length being represented by L when p is expressed in binary notation, comprising:
an (xcex1, xcex2) extraction section for calculating an integer pair (xcex1, xcex2) satisfying C=xcex1Rxe2x80x2+xcex2 on the basis of C and R when w represents a word length and Rxe2x80x2 represents a value obtained by dividing R by 2w;
a multiplication section for obtaining xcex5xcex2 by multiplying an integer xcex5 satisfying Rxe2x80x2xe2x88x921=xcex5(mod p) and xcex2 calculated by the (xcex1, xcex2) extraction section;
an addition section for obtaining xcex1+xcex5xcex2 by adding xcex1 calculated by the (xcex1, xcex2) extraction section and xcex5xcex2 calculated by the multiplication section; and
a calculation section for obtaining (xcex1+xcex5xcex2), 2xe2x88x92w(mod p) on the basis of xcex1+xcex5xcex2 obtained by the addition section and w.
According to the present invention, if, for example, xcex5 is a value equal to or less than one word of the computer, the calculation to be performed by the multiplication section is a multiplication of a 1-word integer and a multiple-length integer. In addition, the execution result obtained by the addition section becomes larger by about one word. The last calculation section can be implemented by Montgomery reduction operation for reducing the data by the lowermost one word, i.e., the processing amount corresponding to a multiplication of a 1-word integer and a multiple-length integer. Since the computation size in other portions is small, a reduction in the overall processing amount can be achieved.
According to the third aspect of the present invention, there is provided a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=Cxc2x7Rxe2x88x921 mod p by using R defined as R=2n using an integer n falling within a range nxe2x89xa7L with a bit length being represented by L when p is expressed in binary notation, comprising:
an (xcex1, xcex2) extraction section for calculating an integer pair (xcex1, xcex2) satisfying C=xcex1R+xcex2 on the basis of C and R;
a multiplication section for calculating xcex5xcex2 by multiplying xcex5 satisfying Rxe2x80x2xe2x88x921=xcex5 (mod p) when w represents a word length and Rxe2x80x2 represents a value obtained by dividing R by 2w and xcex2 extracted by the (xcex1, xcex2) extraction section; and
a calculation section for obtaining E=xcex5xcex22xe2x88x92w(mod p) on the basis of xcex5xcex2 obtained by the multiplication section and w, and obtaining xcex1+E(mod p) on the basis of obtained E and a calculated by the (xcex1, xcex2) extraction section.
According to the present invention, if, for example, xcex5 is a value equal to or less than one word of the computer, the calculation to be performed by the multiplication section is a multiplication of a 1-word integer and a multiple-length integer. The calculation section for E can be implemented by Montgomery reduction operation for reducing the data by the lowermost one word, i.e., the processing amount corresponding to a multiplication of a 1-word integer and a multiple-length integer. Since the computation size in other portions is small, a reduction in the overall processing amount can be achieved.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.